package first.niuke.midding;

/**
 * @ClassName NC59
 * @description:
 * @author: 荣燊
 * @create: 2021-06-16 22:14
 **/
public class NC59 {
    public static void main(String[] args) {
        int[][] ints = {
                        {1,3,5,9},
                        {8,1,3,4},
                        {5,0,6,1},
                        {8,8,4,0}};
        System.out.println(minPathSum(ints));

    }

    // 矩阵的最小路径和，动态规划
    // dp[i][j]:表示走到第i,j的最小路径
    // dp[i][j] = arr[i][j] + min{dp[i-1][j],dp[i][j-1]}
    public static int minPathSum (int[][] matrix) {
        // write code here
        // 1.创建dp二元数组
        int[][] dp = new int[matrix.length][matrix[0].length];
        dp[0][0] = matrix[0][0];
        // 将第一行更新完
        for (int i=1; i<matrix[0].length; i++) {
            dp[0][i] = matrix[0][i] + dp[0][i-1];
        }
        // 将第一列更新
        for (int j=1; j<matrix.length; j++) {
            dp[j][0] = matrix[j][0] + dp[j-1][0];
        }
        // 更新其他列
        for (int i=1; i<matrix.length; i++) {
            for (int j=1; j<matrix[0].length; j++) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[matrix.length-1][matrix[0].length-1];

    }

}
